package pers.lls.hds.map;


/**
 * 深度优先搜索
 *
 * @author lilichai
 */
public class DfsGraph {
    private final int MAX_VERTS = 20;
    private DfsVertex DfsVertexList[];
    private int adjMat[][];
    private int nVerts;
    private DfsStackX theStack;

    public DfsGraph() {
        DfsVertexList = new DfsVertex[MAX_VERTS];

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int y = 0; y < MAX_VERTS; y++) {
            for (int x = 0; x < MAX_VERTS; x++) {
                adjMat[x][y] = 0;
            }
        }
        theStack = new DfsStackX();
    }

    public void addDfsVertex(char lab) {
        DfsVertexList[nVerts++] = new DfsVertex(lab);
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }

    public void displayDfsVertex(int v) {
        System.out.print(DfsVertexList[v].label);
    }

    public void dfs() {
        DfsVertexList[0].wasVisited = true;
        displayDfsVertex(0);
        theStack.push(0);

        while (!theStack.isEmpty()) {

            int v = getAdjUnvisitedDfsVertex(theStack.peek());
            if (v == -1) {
                theStack.pop();
            } else {
                DfsVertexList[v].wasVisited = true;
                displayDfsVertex(v);
                theStack.push(v);
            }
        }

        for (int j = 0; j < nVerts; j++) {
            DfsVertexList[j].wasVisited = false;
        }
    }

    public int getAdjUnvisitedDfsVertex(int v) {
        for (int j = 0; j < nVerts; j++) {
            if (adjMat[v][j] == 1 && DfsVertexList[j].wasVisited == false) {
                return j;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        DfsGraph theDfsGraph = new DfsGraph();
        theDfsGraph.addDfsVertex('A');
        theDfsGraph.addDfsVertex('B');
        theDfsGraph.addDfsVertex('C');
        theDfsGraph.addDfsVertex('D');
        theDfsGraph.addDfsVertex('E');

        theDfsGraph.addEdge(0, 1);
        theDfsGraph.addEdge(1, 2);
        theDfsGraph.addEdge(0, 3);
        theDfsGraph.addEdge(3, 4);

        System.out.print("Visits: ");
        theDfsGraph.dfs();
        System.out.println();
    }

}

class DfsStackX {
    private final int SIZE = 20;
    private int[] st;
    private int top;

    public DfsStackX() {
        st = new int[SIZE];
        top = -1;
    }

    public void push(int j) {
        st[++top] = j;
    }

    public int pop() {
        return st[top--];
    }

    public int peek() {
        return st[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

}

class DfsVertex {
    public char label;
    public boolean wasVisited;

    public DfsVertex(char lab) {
        label = lab;
        wasVisited = false;
    }

}


